7/13
总结:只会做水题
题目链接
A
- 建图bfs,把 $\rm (sum, mod)$ 看成每个点的状态。
- 可以发现的是长度可以很长,但对于同一个 $\rm sum$ 余数只有 $\rm [0,9]$ 这十种,故状态数最多 $d·s$ 种。
B
题意
题解
C
- 显然是线段树的题,赛时想了没想出怎么保证复杂度。
- 实际上,设置区间的 $\rm max,min,lazy$。
- 一开始建树将所有点赋值为 $k$, 若一个区间 $max\geq $ 更新的数量,直接对这个区间进行 $\rm lazy$标记。反之,则递归更新直接更新到底,虽然这样看起来很费时,实际上更新到底的节点(天)以后都不用再更新了,因为需要的量已经够了。
- 实际上就是一个线段树区间 $max, min, lazy$ 组合题。
D
模拟即可
E
- 一个直观的感觉是, $d$ 太大会使得很多任务都要做,这样可能不是最优,因为耽误了可能 $d$ 更小的没做,不是最优解。$d$ 太小的话会使很多任务不能做,导致时间用不完,不是最优解。
- 故可先二分一个最大 $d$ 使得完成所有能完成的任务在 $t$ 时间内,但这可能不是最优的,因为可能 $d$ 稍微大一点,虽然不能完成所有能完成的任务在 $d$ 时间内,但多完成了一些在 $d$ 较小的时候没有完成的,最优解只可能在这两者之间。
- 故二分最大 $d$, 最优再判一下 $d+1$ 和 $d$ 谁最优。
F
贪心即可
G
题意
题解
H
模拟即可
I
题意
题解
J
题意
题解
K
模拟即可